package com.liunian.algorithmstudy.greedy;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PartitionLabels763 {

	/**
	 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
	 例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
	 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
	 返回一个表示每个字符串片段的长度的列表。

	 示例 1：
	 输入：s = "ababcbacadefegdehijhklij"
	 输出：[9,7,8]
	 解释：
	 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
	 每个字母最多出现在一个片段中。
	 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

	 示例 2：
	 输入：s = "eccbbbbdec"
	 输出：[10]
	 */
	public List<Integer> partitionLabels(String s) {
		List<Integer> res = new ArrayList<>();
		int[] position = new int[26];
		for (int i = 0; i < s.length(); i++) {
			position[s.charAt(i) - 'a'] = i;
		}
		int right = 0;
		int left = 0;
		for (int i = 0; i < s.length(); i++) {
			right = Math.max(right, position[s.charAt(i) - 'a']);
			if (i == right) {
				res.add(right - left + 1);
				left = right + 1;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		PartitionLabels763 labels = new PartitionLabels763();
		System.out.println(labels.partitionLabels("ababcbacadefegdehijhklij"));
	}

}
